#include <string.h>
#include <strings.h>
#include <assert.h>

#include "globals.h"
#include "heapsort.h"


/*
Ordenamiento por propiedad heap.

1er parámetro: Array de palabras.

2do parámetro: Cantidad de palabras.


devuelve: -.
*/
void tp1_heapsort(char* words[], int n)
{

        /* Testeo la validéz de los parámetros. */
#ifdef DEBUG
        assert (n > 0);
        assert (words != NULL);
#endif

        /* Implementación tomada directamente del pseudocódigo del libro de Knuth. */
        int i = n, j = n/2, parent, child;
        char* t;

        while (true)
        {
                /* El loop sigue hasta que el array esta ordenado. */
                if (j > 0)   					/* Primera etapa - Ordenado del heap. */
                {
                        t = words[--j];				/* Salvo el nuevo "padre". */
                }
                else         					/* Segunda etapa - Extrayendo  elementos "in-place". */
                {
                        if (--i == 0)				/* "Achico" el heap con el que se trabaja. */
                                break; 				/* Cuando el heap esta vacío, el array está ordenado */

                        t = words[i];				/* Salvo el último valor (se va a sobreescribir). */
                        words[i] = words[0]; 			/* Salvo el valor mayor al final del array. */
                }

                parent = j; 					/* Comienzo el "corrimiento" hacia abajo desde el padre. */
                child = j*2 + 1;				/* Posición del "hijo" izquierdo. */

                /* Operación de desplazamiento - "corriendo" el valor de t hacia abajo en el heap. */
                while (child < i)
                {
                        if ((child + 1) < i  &&  (compare_str(words[child + 1], words[child]) > 0))
                        {
                                child++;			/* Selecciono el mayor "hijo". */
                        }

                        if (compare_str(words[child], t) > 0)	/* Si cualquiera de los "hijos" es mayor que el "padre". */
                        {
                                words[parent] = words[child]; 	/* Muevo el "hijo mayor" hacia arriba. */
                                parent = child;			/* Muevo el "padre" hacia este "hijo". */
                                child = parent*2+1; 		/* Posición del nuevo "hijo" en el heap. */
                        }
                        else
                        {
                                break; 				/* Se encontró el lugar de t. */
                        }
                }

                words[parent] = t; 				/* Salvo t en el heap. */
        }
}
